package basic.study.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @ClassName Mid129
 * @Description 课程表
 * @Company inspur
 * @Author Kevin
 * @Date 2020/7/8 11:51
 * @Version 1.0
 */
public class Mid129 {
    class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            //构建入度表
            int[] indegrees = new int[numCourses];
            //边缘列表
            List<List<Integer>> adjacency = new ArrayList<>();
            //BFS用的Queue
            Queue<Integer> queue = new LinkedList<>();

            //初始化
            for (int i = 0; i < numCourses; i++) {
                adjacency.add(new ArrayList<>());
            }
            for (int[] cp: prerequisites) {
                //增加入度
                indegrees[cp[0]]++;
                //bfs下一节点集
                adjacency.get(cp[1]).add(cp[0]);
            }
            //将入度为0的加入队列
            for (int i = 0; i < numCourses; i++) {
                if (indegrees[i] == 0) {
                    queue.offer(i);
                }
            }

            //BFS
            while (!queue.isEmpty()) {
                int node = queue.poll();
                numCourses--;
                for (int cp: adjacency.get(node)) {
                    if (--indegrees[cp] == 0) {
                        queue.offer(cp);
                    }
                }
            }
            return numCourses == 0;
        }
    }
}
